#include <string>
#include <vector>
#include <sstream>
using namespace std;
class Solution {
public:
    string getPermutation(int n, int k) {
        vector<bool> used(10, false);
        int p[10]={1};
        for (int i=1;i<=9;i++) p[i]=p[i-1]*i;
        --k;
        stringstream ret;
        for (int i=n-1;i>=0;i--) {
            for (int j=k/p[i], q=1;q<=9;q++)
                if (!used[q]) {
                    --j;
                    if (j<0) {
                        ret<<q;
                        used[q]=true;
                        break;
                    }
                }
            k=k%p[i];
        }
        return ret.str();
    }
};
